<head>
    <meta charset="UTF-8">
<title>入门训练 Fibonacci数列</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div class="sec_header">
问题描述</div>
<div class="sec_cont">
	<p>Fibonacci数列的递推公式为：F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub>，其中F<sub>1</sub>=F<sub>2</sub>=1。</p>
	<p>当n比较大时，F<sub>n</sub>也非常大，现在我们想知道，F<sub>n</sub>除以10007的余数是多少。</p>
</div>
<div class="sec_header">
输入格式</div>
<div class="sec_cont">
	输入包含一个整数n。</div>
<div class="sec_header">
输出格式</div>
<div class="sec_cont">
	输出一行，包含一个整数，表示F<sub>n</sub>除以10007的余数。
	<div class="sec_note">
	<p>说明：在本题中，答案是要求F<sub>n</sub>除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出F<sub>n</sub>的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。</p>
	</div>
</div>
<div class="sec_header">
样例输入</div>
<div class="sec_text">
	10</div>
<div class="sec_header">
样例输出</div>
<div class="sec_text">
	55</div>
<div class="sec_header">
样例输入</div>
<div class="sec_text">
	22</div>
<div class="sec_header">
样例输出</div>
<div class="sec_text">
	7704</div>
<div class="sec_header">
数据规模与约定</div>
<div class="sec_cont">
	1 &lt;= n &lt;= 1,000,000。</div>
